package LC_plus;

public class LC706 {
    //链表节点
    private class Node {
        int key;
        int value;
        Node next;

        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    //数组长度
    private final int N = 10000;
    private Node[] node;

    public LC706() {
        node = new Node[N];
    }

    //哈希函数
    private int hash(int key) {
        return key % N;
    }

    public void put(int key, int value) {
        int hash = hash(key);
        if (node[hash] == null) {
            //先存虚拟头
            node[hash] = new Node(-1, -1);
            //再存实际头节点
            node[hash].next = new Node(key, value);
        } else {
            //从虚拟头开始遍历
            Node prev = node[hash];
            while (prev.next != null) {
                if (prev.next.key == key) {
                    //有键，更新值
                    prev.next.value = value;
                    return;
                }
                prev = prev.next;
            }
            //没有键，添加节点
            prev.next = new Node(key, value);
        }
    }

    public int get(int key) {
        int hash = hash(key);
        if (node[hash] != null) {
            Node cur = node[hash].next;
            while (cur != null) {
                if (cur.key == key) {
                    return cur.value;
                }
                cur = cur.next;
            }
        }
        return -1;
    }

    public void remove(int key) {
        int hash = hash(key);
        if (node[hash] != null) {
            Node prev = node[hash];
            while (prev.next != null) {
                //删除节点
                if (prev.next.key == key) {
                    Node delNode = prev.next;
                    prev.next = delNode.next;
                    delNode.next = null;
                    return;
                }
                prev = prev.next;
            }
        }
    }
}
